Because of the rapid growth rate of the electronics industry, each year integrated circuits are required to be smaller, more dense, and faster than before. Integrated circuits can be extremely complex, with millions of transistors on a single chip. Typically one needs to minimize some property of the circuit--for example, the size of the circuit or the power dissipated by the circuit--while preserving a rapid response time. Optimizing the circuit in the face of the extreme complexity of the circuit is therefore a difficult problem.
The integrated circuit constantly undergoes transitions in which some of the active elements of the circuit change state from a logical "low" to a logical "high," and other elements change from "high" to "low." After one such transition takes place, some time must elapse for the remainder of the circuit to equilibrate before another transition can occur. The amount of time that must elapse is the response time of the circuit, and this response time in general depends on the transition. When attempting to optimize the circuit, the transition corresponding to the slowest response time, or else several transitions simultaneously, are considered.
Conventional approaches to the optimization problem estimate the response time of the circuit by the Elmore delay of one or more transitions of the circuit. Such approaches are disclosed, for example, in Pillage, Ratzlaff, and Gopal, U.S. Pat. No. 5,379,231, and in Dunlop and Fishburn, U.S. Pat. No. 4,827,428. Sizes of elements of the circuit are optimized with respect to a certain property of the circuit, while keeping the Elmore delay suitably small. A severe limitation of these methods, however, is that the Elmore delay cannot be used for a circuit that has a non-tree topology. In other words, if the circuit has loops, the above methods cannot be used.
A typical solution is to simply ignore the non-tree nature of the circuit, and use the Elmore delay methods anyway. In this approach, circuit interconnects that form loops in the circuit are ignored during the optimization procedure. However, as the circuits get smaller and smaller, crosstalk between the elements becomes increasingly import ant. Because of the crosstalk, the circuits effectively comprise loops, even if the circuits are manufactured with an intended tree topology. Pre sent methods do not allow the crosstalk, or any other loops, to be taken into account when designing an optimum layout of the circuit.
Another disadvantage of the conventional methods is that the topology of the circuit must be fixed in advance, and cannot be determined as part of the optimization procedure. It is desirable to have a method for designing integrated circuits that not only optimizes the sizes of the elements, but determines which connections are necessary and which should be omitted in the optimum case. Such flexibility is not possible when the Elmore delay methods are used.